Introduction

Machine learning is an application of artificial intelligence (AI) that provides systems the ability to automatically learn and improve from experience without being explicitly programmed. Machine learning focuses on the development of computer programs that can access data and use it learn for themselve.

There are three different task done by the Machine Learning Algorithms

  1. Classifiaction.
  2. Clustering.
  3. Regression.

This article is confined to classification.

What is classification ?

This is the problem of identifing to which set of categories my new observation Belongs.The goal of classification is to find Boundaries that best separate different categories of data.

Type of classification.

There are two type of classification.

1)Binary Classification. This type of classification is done when we have only 2 class to classify.

2)Multi-class classification. This type of classification is done when we have more than 2 class to classify.

Today we are going to deal with Multi-class classification problem by XGBoost.

problem Statment.

There is a device which has collected the data ,now the device needs to dedicate any new floor by the help of previous data.

Solution

we are going to use Machine Learning Algorithms and build a prediction model for this device which can predict on which floor it’s standing by collecting the properties of the floor.

library ’s used.

library(data.table)
library(ggplot2)
library(plotly)
library(dplyr)
library(corrplot)
library(kableExtra)
library(mltools)
library(caTools)
library(xgboost)
library(Ckmeans.1d.dp) 
library(Matrix)
library(readr)
library(car)
library(caret)
library(lattice)
#The package for random forest function
library(MASS)
library(randomForest)
#correlation plot
library(corrplot)

Importing all the data set into R.we are dropping the row_id, group_id as all the variables in this column are unique,so this does not come handy for our analysis.

train_data<-merge(x_train,y_train,by="series_id")

Viewing the structure of the both training and testing data.

str(x_train)
Classes ‘data.table’ and 'data.frame':  487680 obs. of  12 variables:
 $ series_id            : int  0 0 0 0 0 0 0 0 0 0 ...
 $ measurement_number   : int  0 1 2 3 4 5 6 7 8 9 ...
 $ orientation_X        : num  -0.759 -0.759 -0.759 -0.759 -0.759 ...
 $ orientation_Y        : num  -0.634 -0.634 -0.634 -0.634 -0.634 ...
 $ orientation_Z        : num  -0.105 -0.105 -0.105 -0.105 -0.105 ...
 $ orientation_W        : num  -0.106 -0.106 -0.106 -0.106 -0.106 ...
 $ angular_velocity_X   : num  0.10765 0.06785 0.00727 -0.01305 0.00513 ...
 $ angular_velocity_Y   : num  0.01756 0.02994 0.02893 0.01945 0.00765 ...
 $ angular_velocity_Z   : num  0.000767 0.003386 -0.005978 -0.008974 0.005245 ...
 $ linear_acceleration_X: num  -0.749 0.34 -0.264 0.427 -0.51 ...
 $ linear_acceleration_Y: num  2.1 1.51 1.59 1.1 1.47 ...
 $ linear_acceleration_Z: num  -9.75 -9.41 -8.73 -10.1 -10.44 ...
 - attr(*, ".internal.selfref")=<externalptr> 
str(y_train)
Classes ‘data.table’ and 'data.frame':  3810 obs. of  2 variables:
 $ series_id: int  0 1 2 3 4 5 6 7 8 9 ...
 $ surface  : Factor w/ 9 levels "carpet","concrete",..: 3 2 2 2 7 8 6 2 5 8 ...
 - attr(*, ".internal.selfref")=<externalptr> 

Now we are going to join x_train and y_train by series_id.

train_data<-merge(x_train,y_train,by="series_id")

Seing the columns names.

colnames(train_data)
 [1] "series_id"             "measurement_number"    "orientation_X"         "orientation_Y"         "orientation_Z"        
 [6] "orientation_W"         "angular_velocity_X"    "angular_velocity_Y"    "angular_velocity_Z"    "linear_acceleration_X"
[11] "linear_acceleration_Y" "linear_acceleration_Z" "surface"              

so these are our feature where “Surface”" is our target feature and all others act as predictors in our model building.

Lets check how many types of floor do we have.

table(train_data$surface)

                carpet               concrete          fine_concrete             hard_tiles hard_tiles_large_space               soft_pvc 
                 24192                  99712                  46464                   2688                  39424                  93696 
            soft_tiles                  tiled                   wood 
                 38016                  65792                  77696 

so we have 9 Types of floor.

so we need to do multiclass classification.

Data Cleaning

Summary of the data.

summary(train_data)
   series_id    measurement_number orientation_X      orientation_Y      orientation_Z      orientation_W       angular_velocity_X  
 Min.   :   0   Min.   :  0.00     Min.   :-0.98910   Min.   :-0.98965   Min.   :-0.16283   Min.   :-0.156620   Min.   :-2.3710000  
 1st Qu.: 952   1st Qu.: 31.75     1st Qu.:-0.70512   1st Qu.:-0.68898   1st Qu.:-0.08947   1st Qu.:-0.106060   1st Qu.:-0.0407520  
 Median :1904   Median : 63.50     Median :-0.10596   Median : 0.23786   Median : 0.03195   Median :-0.018704   Median : 0.0000842  
 Mean   :1904   Mean   : 63.50     Mean   :-0.01805   Mean   : 0.07506   Mean   : 0.01246   Mean   :-0.003804   Mean   : 0.0001775  
 3rd Qu.:2857   3rd Qu.: 95.25     3rd Qu.: 0.65180   3rd Qu.: 0.80955   3rd Qu.: 0.12287   3rd Qu.: 0.097215   3rd Qu.: 0.0405272  
 Max.   :3809   Max.   :127.00     Max.   : 0.98910   Max.   : 0.98898   Max.   : 0.15571   Max.   : 0.154770   Max.   : 2.2822000  
                                                                                                                                    
 angular_velocity_Y  angular_velocity_Z  linear_acceleration_X linear_acceleration_Y linear_acceleration_Z                   surface     
 Min.   :-0.927860   Min.   :-1.268800   Min.   :-36.0670      Min.   :-121.490      Min.   :-75.386       concrete              :99712  
 1st Qu.:-0.033191   1st Qu.:-0.090743   1st Qu.: -0.5308      1st Qu.:   1.958      1st Qu.:-10.193       soft_pvc              :93696  
 Median : 0.005412   Median :-0.005335   Median :  0.1250      Median :   2.880      Median : -9.365       wood                  :77696  
 Mean   : 0.008338   Mean   :-0.019184   Mean   :  0.1293      Mean   :   2.886      Mean   : -9.365       tiled                 :65792  
 3rd Qu.: 0.048068   3rd Qu.: 0.064604   3rd Qu.:  0.7923      3rd Qu.:   3.799      3rd Qu.: -8.523       fine_concrete         :46464  
 Max.   : 1.079100   Max.   : 1.387300   Max.   : 36.7970      Max.   :  73.008      Max.   : 65.839       hard_tiles_large_space:39424  
                                                                                                           (Other)               :64896  

Now checking the NA ’s and Empty spaces in the data.

cat("\nThe Total number of NA 's in the train data is :- ",sum(is.na(train_data)))

The Total number of NA 's in the train data is :-  0
cat("\nThe Total number of empty spaces 's in the train data is :- ",sum(train_data==" "))

The Total number of empty spaces 's in the train data is :-  0

Checking the percentage of each class in the surface feature(Target Variable),checking the ImmBalanced class.

#Donet chart which display the percentage of each class in the column
 p <- train_data %>%
  group_by(surface) %>%
  summarize(count = n()) %>%
  plot_ly(labels = ~surface, values = ~count) %>%
  add_pie(hole = 0.6) %>%
  layout(title = "The Percentage of category at Surface column",  showlegend = F,
         xaxis = list(showgrid = FALSE, zeroline = FALSE, showticklabels = FALSE),
         yaxis = list(showgrid = FALSE, zeroline = FALSE, showticklabels = FALSE))
p

As each categories are distributed uniformly ,so there is no problem of miss classification.

Encoding the target variable.

train_data$surface <-as.numeric(as.factor(train_data$surface))-1

Actual Values Encoded Values

carpet 0 concrete 99712 1 fine_concrete 46464 2 hard_tiles 2688 3 hard_tiles_large_space 39424 4 soft_pvc 93696 5 soft_tiles 38016 6 tiled 65792 7 wood 7 8

corr<-cor(x_train)
corrplot(corr,type = "lower")

There are high positive correlation between the predictor variable orientation_w with orientation_x,orientation_z with orientation_y and there is high negative correlation between the predictor variables angular_velocity_y and angular_velocity_z.

As we are using XGBoost for our model building so we does not need to handle multicollinearity as XGBoost can handle it by it self.

The XGBoost Model Building

Dividing the data set into train test.

set.seed(1)
## 75% of the sample size
smp_size <- floor(0.75 * nrow(train_data))
## set the seed to make your partition reproducible
set.seed(123)
train_ind <- sample(seq_len(nrow(train_data)), size = smp_size)
train_train_data <- train_data[train_ind,]
test_train_data <- train_data[-train_ind,]

Now checking the classs imbalance in the training data.

#Donet chart which display the percentage of each class in the column
 p <- train_train_data %>%
  group_by(surface) %>%
  summarize(count = n()) %>%
  plot_ly(labels = ~surface, values = ~count) %>%
  add_pie(hole = 0.6) %>%
  layout(title = "The Percentage of category at Surface column",  showlegend = F,
         xaxis = list(showgrid = FALSE, zeroline = FALSE, showticklabels = FALSE),
         yaxis = list(showgrid = FALSE, zeroline = FALSE, showticklabels = FALSE))
p

As we see all the categorical variables are properly balanced ,so now we use this train_train_data for Model Building.

Now applying XGBoost algorithm for classification.

preparing the data for xgboost algorithm. note :- XGBoost can not handle categorical or numeric data. we should always pass the data in for of matrix for xgboost.

dtrain <- xgb.DMatrix(as.matrix(train_train_data[,-"surface"]), label = as.matrix(train_train_data$surface))
dtestfinal<-xgb.DMatrix(as.matrix(test_train_data[,-"surface"]), label = as.matrix(test_train_data$surface))

Setting parameters for xgboost

#default parameters
params <- list(booster = "gbtree",num_class=9 ,objective = "multi:softmax", eta=0.2, max_depth=4, min_child_weight=2, subsample=1, colsample_bytree=1)

Doing parameter tuning

#find best nround
cv<-xgb.cv( params = params, data = dtrain, nrounds = 50, nfold = 5,gamma=0, showsd = T, stratified = T, print.every.n = 10, early.stop.round = 20, maximize = F)
'print.every.n' is deprecated.
Use 'print_every_n' instead.
See help("Deprecated") and help("xgboost-deprecated").'early.stop.round' is deprecated.
Use 'early_stopping_rounds' instead.
See help("Deprecated") and help("xgboost-deprecated").
[1] train-merror:0.351930+0.002603  test-merror:0.352816+0.003646 
Multiple eval metrics are present. Will use test_merror for early stopping.
Will train until test_merror hasn't improved in 20 rounds.

[11]    train-merror:0.214109+0.003833  test-merror:0.215639+0.005167 
[21]    train-merror:0.172163+0.002382  test-merror:0.174437+0.003537 
[31]    train-merror:0.142943+0.002307  test-merror:0.145601+0.002569 
[41]    train-merror:0.124097+0.001695  test-merror:0.127124+0.001975 
[50]    train-merror:0.111857+0.000658  test-merror:0.115286+0.000921 
cv$best_iteration
[1] 50
print(cv)
##### xgb.cv 5-folds
Best iteration:
print(cv, verbose=TRUE)
##### xgb.cv 5-folds
call:
  xgb.cv(params = params, data = dtrain, nrounds = 50, nfold = 5, 
    showsd = T, stratified = T, maximize = F, gamma = 0, print.every.n = 10, 
    early.stop.round = 20)
params (as set within xgb.cv):
  booster = "gbtree", num_class = "9", objective = "multi:softmax", eta = "0.2", max_depth = "4", min_child_weight = "2", subsample = "1", colsample_bytree = "1", gamma = "0", print_every_n = "10", early_stop_round = "20", silent = "1"
callbacks:
  cb.print.evaluation(period = print_every_n, showsd = showsd)
  cb.evaluation.log()
  cb.early.stop(stopping_rounds = early_stopping_rounds, maximize = maximize, 
    verbose = verbose)
niter: 50
best_iteration: 50
best_ntreelimit: 50
evaluation_log:
Best iteration:

As we in the above output we got minimum error iteration 50.

Now training the model on train data set.

#first default - model training
xgb1 <- xgb.train (params = params, data = dtrain, nrounds = 50, watchlist = list(val=dtestfinal,train=dtrain), print.every.n = 10, early.stop.round = 10, maximize = F , eval_metric = "mlogloss")
'print.every.n' is deprecated.
Use 'print_every_n' instead.
See help("Deprecated") and help("xgboost-deprecated").'early.stop.round' is deprecated.
Use 'early_stopping_rounds' instead.
See help("Deprecated") and help("xgboost-deprecated").
[1] val-mlogloss:1.855254   train-mlogloss:1.854063 
Multiple eval metrics are present. Will use train_mlogloss for early stopping.
Will train until train_mlogloss hasn't improved in 10 rounds.

[11]    val-mlogloss:0.931260   train-mlogloss:0.926395 
[21]    val-mlogloss:0.676190   train-mlogloss:0.670568 
[31]    val-mlogloss:0.547322   train-mlogloss:0.541441 
[41]    val-mlogloss:0.469425   train-mlogloss:0.463405 
[50]    val-mlogloss:0.417579   train-mlogloss:0.411473 

Now we are using our model on test data set.

#model prediction
xgbpred <- predict (xgb1,dtestfinal)

Confusion Matrix

checking the results of the model.

result<-confusionMatrix(table(as.factor(test_train_data$surface), as.factor(xgbpred)),mode = "prec_recall")
result
Confusion Matrix and Statistics

   
        0     1     2     3     4     5     6     7     8
  0  4698   646     8     0     0     0   131   107   455
  1    28 22376   383     0   333   453   218   351   835
  2     0   496 10035    24    84   205    43   466   382
  3     0     0     4   687     0     0    38     3     0
  4    23   871   180     0  8309    74     0    29   246
  5   253   627   222     0    69 20825   473   316   419
  6    81   162    19    42     0   340  8906   153    32
  7    77   191   249    36    22   529   134 15059    48
  8   144  1256   389     0   231   499    37    14 16845

Overall Statistics
                                          
               Accuracy : 0.8837          
                 95% CI : (0.8819, 0.8855)
    No Information Rate : 0.2184          
    P-Value [Acc > NIR] : < 2.2e-16       
                                          
                  Kappa : 0.8636          
                                          
 Mcnemar's Test P-Value : NA              

Statistics by Class:

                     Class: 0 Class: 1 Class: 2 Class: 3 Class: 4 Class: 5 Class: 6 Class: 7 Class: 8
Precision             0.77717   0.8959  0.85513 0.938525  0.85378   0.8975  0.91484   0.9213   0.8676
Recall                0.88575   0.8404  0.87344 0.870722  0.91832   0.9084  0.89238   0.9128   0.8745
F1                    0.82791   0.8673  0.86419 0.903353  0.88488   0.9029  0.90347   0.9170   0.8711
Prevalence            0.04350   0.2184  0.09423 0.006471  0.07421   0.1880  0.08186   0.1353   0.1580
Detection Rate        0.03853   0.1835  0.08231 0.005635  0.06815   0.1708  0.07305   0.1235   0.1382
Detection Prevalence  0.04958   0.2049  0.09625 0.006004  0.07982   0.1903  0.07985   0.1341   0.1592
Balanced Accuracy     0.93710   0.9066  0.92902 0.935175  0.95286   0.9422  0.94249   0.9503   0.9247

Our Model has given accuracy of 88%.

The important features given by XGBoost

xgb.importance( model =xgb1)

As we see above the orientation_x is the most important feature for predicting the type of floor.

Now we are going to use our model for predicting the test data. preprocessing the test data.

dtestfinal<-xgb.DMatrix(as.matrix(test))

Using the model for Test Data

predicting the values for the Test data .

predicted_value<-predict (xgb1,dtestfinal)
class(predicted_value)
[1] "numeric"

Function for decoding the variables.

Decoding<-function(x){
  if(x==0){
    return("carpet")
  }else if(x==1){
    return("concrete")
  }else if(x==2){
    return("fine_concrete")
  }else if(x==3){
    return("hard_tiles")
  }else if(x==4){
    return("hard_tiles_large_space ")
  }else if(x==5){
    return("soft_pvc")
  }else if(x==6){
    return("soft_tiles")
  }else if(x==7){
    return("tiled")
  }else{
    return("wood")
  }
}

carpet 0 concrete 1 fine_concrete 2 hard_tiles 3 hard_tiles_large_space 4 soft_pvc 5 soft_tiles 6 tiled 7 wood 8

Now we are doing Decoding our target variable to their respective categories given above .

predicted_value<-sapply(predicted_value,Decoding)

so Final predictions are :-

test$surface<-as.factor(predicted_value)

Viewing the test data after predictions.

The OutPut.

This is the following expected output.

LS0tDQp0aXRsZTogIkZsb29yIHByZWRpY3Rpb24gQnkgWEdCb29zdCINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCiNJbnRyb2R1Y3Rpb24NCg0KTWFjaGluZSBsZWFybmluZyBpcyBhbiBhcHBsaWNhdGlvbiBvZiBhcnRpZmljaWFsIGludGVsbGlnZW5jZSAoQUkpIHRoYXQgcHJvdmlkZXMgc3lzdGVtcyB0aGUgYWJpbGl0eSB0byBhdXRvbWF0aWNhbGx5IGxlYXJuIGFuZCBpbXByb3ZlIGZyb20gZXhwZXJpZW5jZSB3aXRob3V0IGJlaW5nIGV4cGxpY2l0bHkgcHJvZ3JhbW1lZC4gTWFjaGluZSBsZWFybmluZyBmb2N1c2VzIG9uIHRoZSBkZXZlbG9wbWVudCBvZiBjb21wdXRlciBwcm9ncmFtcyB0aGF0IGNhbiBhY2Nlc3MgZGF0YSBhbmQgdXNlIGl0IGxlYXJuIGZvciB0aGVtc2VsdmUuDQoNClRoZXJlIGFyZSB0aHJlZSBkaWZmZXJlbnQgdGFzayBkb25lIGJ5IHRoZSBNYWNoaW5lIExlYXJuaW5nIEFsZ29yaXRobXMNCg0KMSkgQ2xhc3NpZmlhY3Rpb24uDQoyKSBDbHVzdGVyaW5nLg0KMykgUmVncmVzc2lvbi4NCg0KVGhpcyBhcnRpY2xlIGlzIGNvbmZpbmVkIHRvIGNsYXNzaWZpY2F0aW9uLg0KDQojV2hhdCBpcyBjbGFzc2lmaWNhdGlvbiA/DQpUaGlzIGlzIHRoZSBwcm9ibGVtIG9mIGlkZW50aWZpbmcgdG8gd2hpY2ggc2V0IG9mIGNhdGVnb3JpZXMgbXkgbmV3IG9ic2VydmF0aW9uIEJlbG9uZ3MuVGhlIGdvYWwgb2YgY2xhc3NpZmljYXRpb24gaXMgdG8gZmluZCBCb3VuZGFyaWVzIHRoYXQgYmVzdCBzZXBhcmF0ZSBkaWZmZXJlbnQgY2F0ZWdvcmllcyBvZiBkYXRhLg0KDQojVHlwZSBvZiBjbGFzc2lmaWNhdGlvbi4NClRoZXJlIGFyZSB0d28gdHlwZSBvZiBjbGFzc2lmaWNhdGlvbi4NCg0KMSlCaW5hcnkgQ2xhc3NpZmljYXRpb24uDQpUaGlzIHR5cGUgb2YgY2xhc3NpZmljYXRpb24gaXMgZG9uZSB3aGVuIHdlIGhhdmUgb25seSAyIGNsYXNzIHRvIGNsYXNzaWZ5Lg0KDQoyKU11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uLg0KVGhpcyB0eXBlIG9mIGNsYXNzaWZpY2F0aW9uIGlzIGRvbmUgd2hlbiB3ZSBoYXZlIG1vcmUgdGhhbiAyIGNsYXNzIHRvIGNsYXNzaWZ5Lg0KDQpUb2RheSB3ZSBhcmUgZ29pbmcgdG8gZGVhbCB3aXRoIE11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0gYnkgWEdCb29zdC4NCg0KI3Byb2JsZW0gU3RhdG1lbnQuDQpUaGVyZSBpcyBhIGRldmljZSB3aGljaCBoYXMgY29sbGVjdGVkIHRoZSBkYXRhICxub3cgdGhlIGRldmljZSBuZWVkcyB0byBkZWRpY2F0ZSBhbnkgbmV3IGZsb29yIGJ5IHRoZSBoZWxwIG9mIHByZXZpb3VzIGRhdGEuDQoNCiNTb2x1dGlvbg0Kd2UgYXJlIGdvaW5nIHRvIHVzZSBNYWNoaW5lIExlYXJuaW5nIEFsZ29yaXRobXMgYW5kIGJ1aWxkIGEgcHJlZGljdGlvbiBtb2RlbCBmb3IgdGhpcyBkZXZpY2Ugd2hpY2ggY2FuIHByZWRpY3Qgb24gd2hpY2ggZmxvb3IgaXQncyBzdGFuZGluZyBieSBjb2xsZWN0aW5nIHRoZSBwcm9wZXJ0aWVzIG9mIHRoZSBmbG9vci4NCg0KDQpsaWJyYXJ5ICdzIHVzZWQuDQpgYGB7cn0NCmxpYnJhcnkoZGF0YS50YWJsZSkNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkocGxvdGx5KQ0KbGlicmFyeShkcGx5cikNCmxpYnJhcnkoY29ycnBsb3QpDQpsaWJyYXJ5KGthYmxlRXh0cmEpDQpsaWJyYXJ5KG1sdG9vbHMpDQpsaWJyYXJ5KGNhVG9vbHMpDQpsaWJyYXJ5KHhnYm9vc3QpDQpsaWJyYXJ5KENrbWVhbnMuMWQuZHApIA0KbGlicmFyeShNYXRyaXgpDQpsaWJyYXJ5KHJlYWRyKQ0KbGlicmFyeShjYXIpDQpsaWJyYXJ5KGNhcmV0KQ0KbGlicmFyeShsYXR0aWNlKQ0KI1RoZSBwYWNrYWdlIGZvciByYW5kb20gZm9yZXN0IGZ1bmN0aW9uDQpsaWJyYXJ5KE1BU1MpDQpsaWJyYXJ5KHJhbmRvbUZvcmVzdCkNCiNjb3JyZWxhdGlvbiBwbG90DQpsaWJyYXJ5KGNvcnJwbG90KQ0KYGBgDQoNCkltcG9ydGluZyBhbGwgdGhlIGRhdGEgc2V0IGludG8gUi53ZSBhcmUgZHJvcHBpbmcgdGhlIHJvd19pZCwgZ3JvdXBfaWQgYXMgYWxsIHRoZSB2YXJpYWJsZXMgaW4gdGhpcyBjb2x1bW4gYXJlIHVuaXF1ZSxzbyB0aGlzIGRvZXMgbm90IGNvbWUgaGFuZHkgZm9yIG91ciBhbmFseXNpcy4gDQpgYGB7cn0NCiNSZWFkaW5nIHRoZSBwcmVkaWN0b3JzLg0KeF90cmFpbjwtZnJlYWQoIlhfdHJhaW4uY3N2IixzdHJpbmdzQXNGYWN0b3JzID0gVCxkcm9wID0gInJvd19pZCIpDQojUmVhZGluZyB0aGUgdGFyZ2V0IHZhcmlhYmxlLg0KeV90cmFpbjwtZnJlYWQoIllfdHJhaW4uY3N2IixzdHJpbmdzQXNGYWN0b3JzID0gVCxkcm9wID0gImdyb3VwX2lkIikNCiNSZWFkaW5nIHRoZSB0ZXN0aW5nIGRhdGENCnRlc3Q8LWZyZWFkKCJYX3Rlc3QuY3N2IixzdHJpbmdzQXNGYWN0b3JzID0gVCxkcm9wID0gInJvd19pZCIpDQpgYGANClZpZXdpbmcgdGhlIHN0cnVjdHVyZSBvZiB0aGUgYm90aCB0cmFpbmluZyBhbmQgdGVzdGluZyBkYXRhLg0KYGBge3J9DQpzdHIoeF90cmFpbikNCnN0cih5X3RyYWluKQ0KYGBgDQpOb3cgd2UgYXJlIGdvaW5nIHRvIGpvaW4geF90cmFpbiBhbmQgeV90cmFpbiBieSBzZXJpZXNfaWQuDQpgYGB7cn0NCnRyYWluX2RhdGE8LW1lcmdlKHhfdHJhaW4seV90cmFpbixieT0ic2VyaWVzX2lkIikNCmBgYA0KDQpTZWluZyB0aGUgY29sdW1ucyBuYW1lcy4NCmBgYHtyfQ0KY29sbmFtZXModHJhaW5fZGF0YSkNCmBgYA0Kc28gdGhlc2UgYXJlIG91ciBmZWF0dXJlIHdoZXJlICJTdXJmYWNlIiIgaXMgb3VyIHRhcmdldCBmZWF0dXJlIGFuZCBhbGwgb3RoZXJzIGFjdCBhcyBwcmVkaWN0b3JzIGluIG91ciBtb2RlbCBidWlsZGluZy4NCg0KTGV0cyBjaGVjayBob3cgbWFueSB0eXBlcyBvZiBmbG9vciBkbyB3ZSBoYXZlLg0KYGBge3J9DQp0YWJsZSh0cmFpbl9kYXRhJHN1cmZhY2UpDQpgYGANCnNvIHdlIGhhdmUgOSBUeXBlcyBvZiBmbG9vci4NCg0Kc28gd2UgbmVlZCB0byBkbyBtdWx0aWNsYXNzIGNsYXNzaWZpY2F0aW9uLg0KDQojRGF0YSBDbGVhbmluZw0KDQpTdW1tYXJ5IG9mIHRoZSBkYXRhLg0KYGBge3J9DQpzdW1tYXJ5KHRyYWluX2RhdGEpDQpgYGANCg0KDQpOb3cgY2hlY2tpbmcgdGhlIE5BICdzIGFuZCBFbXB0eSBzcGFjZXMgIGluIHRoZSBkYXRhLg0KYGBge3J9DQpjYXQoIlxuVGhlIFRvdGFsIG51bWJlciBvZiBOQSAncyBpbiB0aGUgdHJhaW4gZGF0YSBpcyA6LSAiLHN1bShpcy5uYSh0cmFpbl9kYXRhKSkpDQpjYXQoIlxuVGhlIFRvdGFsIG51bWJlciBvZiBlbXB0eSBzcGFjZXMgJ3MgaW4gdGhlIHRyYWluIGRhdGEgaXMgOi0gIixzdW0odHJhaW5fZGF0YT09IiAiKSkNCmBgYA0KQ2hlY2tpbmcgdGhlIHBlcmNlbnRhZ2Ugb2YgZWFjaCBjbGFzcyBpbiB0aGUgc3VyZmFjZSBmZWF0dXJlKFRhcmdldCBWYXJpYWJsZSksY2hlY2tpbmcgdGhlICBJbW1CYWxhbmNlZCBjbGFzcy4NCmBgYHtyfQ0KI0RvbmV0IGNoYXJ0IHdoaWNoIGRpc3BsYXkgdGhlIHBlcmNlbnRhZ2Ugb2YgZWFjaCBjbGFzcyBpbiB0aGUgY29sdW1uDQogcCA8LSB0cmFpbl9kYXRhICU+JQ0KICBncm91cF9ieShzdXJmYWNlKSAlPiUNCiAgc3VtbWFyaXplKGNvdW50ID0gbigpKSAlPiUNCiAgcGxvdF9seShsYWJlbHMgPSB+c3VyZmFjZSwgdmFsdWVzID0gfmNvdW50KSAlPiUNCiAgYWRkX3BpZShob2xlID0gMC42KSAlPiUNCiAgbGF5b3V0KHRpdGxlID0gIlRoZSBQZXJjZW50YWdlIG9mIGNhdGVnb3J5IGF0IFN1cmZhY2UgY29sdW1uIiwgIHNob3dsZWdlbmQgPSBGLA0KICAgICAgICAgeGF4aXMgPSBsaXN0KHNob3dncmlkID0gRkFMU0UsIHplcm9saW5lID0gRkFMU0UsIHNob3d0aWNrbGFiZWxzID0gRkFMU0UpLA0KICAgICAgICAgeWF4aXMgPSBsaXN0KHNob3dncmlkID0gRkFMU0UsIHplcm9saW5lID0gRkFMU0UsIHNob3d0aWNrbGFiZWxzID0gRkFMU0UpKQ0KcA0KYGBgDQpBcyBlYWNoIGNhdGVnb3JpZXMgYXJlIGRpc3RyaWJ1dGVkIHVuaWZvcm1seSAsc28gdGhlcmUgaXMgbm8gcHJvYmxlbSBvZiBtaXNzIGNsYXNzaWZpY2F0aW9uLg0KDQpFbmNvZGluZyB0aGUgdGFyZ2V0IHZhcmlhYmxlLg0KYGBge3J9DQp0cmFpbl9kYXRhJHN1cmZhY2UgPC1hcy5udW1lcmljKGFzLmZhY3Rvcih0cmFpbl9kYXRhJHN1cmZhY2UpKS0xDQpgYGANCg0KQWN0dWFsIFZhbHVlcyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRW5jb2RlZCBWYWx1ZXMNCg0KY2FycGV0ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDANCmNvbmNyZXRlIDk5NzEyICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAxDQpmaW5lX2NvbmNyZXRlIDQ2NDY0ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMg0KaGFyZF90aWxlcyAgMjY4OCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDMNCmhhcmRfdGlsZXNfbGFyZ2Vfc3BhY2UgMzk0MjQgICAgICAgICAgICAgICAgICAgICAgICA0DQpzb2Z0X3B2YyA5MzY5NiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNQ0Kc29mdF90aWxlcyAzODAxNiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDYNCnRpbGVkIDY1NzkyICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA3DQp3b29kIDcgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgOA0KDQpgYGB7cn0NCmNvcnI8LWNvcih4X3RyYWluKQ0KY29ycnBsb3QoY29ycix0eXBlID0gImxvd2VyIikNCmBgYA0KVGhlcmUgYXJlIGhpZ2ggcG9zaXRpdmUgY29ycmVsYXRpb24gYmV0d2VlbiB0aGUgcHJlZGljdG9yIHZhcmlhYmxlIG9yaWVudGF0aW9uX3cgd2l0aCBvcmllbnRhdGlvbl94LG9yaWVudGF0aW9uX3ogd2l0aCBvcmllbnRhdGlvbl95IGFuZCB0aGVyZSBpcyBoaWdoIG5lZ2F0aXZlIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIHByZWRpY3RvciB2YXJpYWJsZXMgYW5ndWxhcl92ZWxvY2l0eV95IGFuZCBhbmd1bGFyX3ZlbG9jaXR5X3ouDQoNCkFzIHdlIGFyZSB1c2luZyBYR0Jvb3N0IGZvciBvdXIgbW9kZWwgYnVpbGRpbmcgc28gd2UgZG9lcyBub3QgIG5lZWQgdG8gaGFuZGxlICBtdWx0aWNvbGxpbmVhcml0eSBhcyBYR0Jvb3N0IGNhbiBoYW5kbGUgaXQgYnkgaXQgc2VsZi4gDQoNCg0KI1RoZSBYR0Jvb3N0IE1vZGVsIEJ1aWxkaW5nDQoNCkRpdmlkaW5nIHRoZSBkYXRhIHNldCBpbnRvIHRyYWluIHRlc3QuDQpgYGB7cn0NCnNldC5zZWVkKDEpDQojIyA3NSUgb2YgdGhlIHNhbXBsZSBzaXplDQpzbXBfc2l6ZSA8LSBmbG9vcigwLjc1ICogbnJvdyh0cmFpbl9kYXRhKSkNCg0KIyMgc2V0IHRoZSBzZWVkIHRvIG1ha2UgeW91ciBwYXJ0aXRpb24gcmVwcm9kdWNpYmxlDQpzZXQuc2VlZCgxMjMpDQp0cmFpbl9pbmQgPC0gc2FtcGxlKHNlcV9sZW4obnJvdyh0cmFpbl9kYXRhKSksIHNpemUgPSBzbXBfc2l6ZSkNCg0KdHJhaW5fdHJhaW5fZGF0YSA8LSB0cmFpbl9kYXRhW3RyYWluX2luZCxdDQp0ZXN0X3RyYWluX2RhdGEgPC0gdHJhaW5fZGF0YVstdHJhaW5faW5kLF0NCmBgYA0KDQpOb3cgY2hlY2tpbmcgdGhlIGNsYXNzcyBpbWJhbGFuY2UgaW4gdGhlIHRyYWluaW5nIGRhdGEuDQpgYGB7cn0NCiNEb25ldCBjaGFydCB3aGljaCBkaXNwbGF5IHRoZSBwZXJjZW50YWdlIG9mIGVhY2ggY2xhc3MgaW4gdGhlIGNvbHVtbg0KIHAgPC0gdHJhaW5fdHJhaW5fZGF0YSAlPiUNCiAgZ3JvdXBfYnkoc3VyZmFjZSkgJT4lDQogIHN1bW1hcml6ZShjb3VudCA9IG4oKSkgJT4lDQogIHBsb3RfbHkobGFiZWxzID0gfnN1cmZhY2UsIHZhbHVlcyA9IH5jb3VudCkgJT4lDQogIGFkZF9waWUoaG9sZSA9IDAuNikgJT4lDQogIGxheW91dCh0aXRsZSA9ICJUaGUgUGVyY2VudGFnZSBvZiBjYXRlZ29yeSBhdCBTdXJmYWNlIGNvbHVtbiIsICBzaG93bGVnZW5kID0gRiwNCiAgICAgICAgIHhheGlzID0gbGlzdChzaG93Z3JpZCA9IEZBTFNFLCB6ZXJvbGluZSA9IEZBTFNFLCBzaG93dGlja2xhYmVscyA9IEZBTFNFKSwNCiAgICAgICAgIHlheGlzID0gbGlzdChzaG93Z3JpZCA9IEZBTFNFLCB6ZXJvbGluZSA9IEZBTFNFLCBzaG93dGlja2xhYmVscyA9IEZBTFNFKSkNCnANCmBgYA0KQXMgd2Ugc2VlIGFsbCB0aGUgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGFyZSBwcm9wZXJseSBiYWxhbmNlZCAsc28gbm93IHdlIHVzZSB0aGlzIHRyYWluX3RyYWluX2RhdGEgZm9yIE1vZGVsIEJ1aWxkaW5nLg0KDQpOb3cgYXBwbHlpbmcgWEdCb29zdCBhbGdvcml0aG0gZm9yIGNsYXNzaWZpY2F0aW9uLg0KDQpwcmVwYXJpbmcgdGhlIGRhdGEgZm9yIHhnYm9vc3QgYWxnb3JpdGhtLg0Kbm90ZSA6LSBYR0Jvb3N0IGNhbiBub3QgaGFuZGxlIGNhdGVnb3JpY2FsIG9yIG51bWVyaWMgZGF0YS4NCndlIHNob3VsZCBhbHdheXMgcGFzcyB0aGUgZGF0YSBpbiBmb3Igb2YgbWF0cml4IGZvciB4Z2Jvb3N0Lg0KYGBge3J9DQpkdHJhaW4gPC0geGdiLkRNYXRyaXgoYXMubWF0cml4KHRyYWluX3RyYWluX2RhdGFbLC0ic3VyZmFjZSJdKSwgbGFiZWwgPSBhcy5tYXRyaXgodHJhaW5fdHJhaW5fZGF0YSRzdXJmYWNlKSkNCmR0ZXN0ZmluYWw8LXhnYi5ETWF0cml4KGFzLm1hdHJpeCh0ZXN0X3RyYWluX2RhdGFbLC0ic3VyZmFjZSJdKSwgbGFiZWwgPSBhcy5tYXRyaXgodGVzdF90cmFpbl9kYXRhJHN1cmZhY2UpKQ0KYGBgDQoNClNldHRpbmcgcGFyYW1ldGVycyBmb3IgeGdib29zdA0KYGBge3J9DQojZGVmYXVsdCBwYXJhbWV0ZXJzDQpwYXJhbXMgPC0gbGlzdChib29zdGVyID0gImdidHJlZSIsbnVtX2NsYXNzPTkgLG9iamVjdGl2ZSA9ICJtdWx0aTpzb2Z0bWF4IiwgZXRhPTAuMiwgbWF4X2RlcHRoPTQsIG1pbl9jaGlsZF93ZWlnaHQ9Miwgc3Vic2FtcGxlPTEsIGNvbHNhbXBsZV9ieXRyZWU9MSkNCmBgYA0KDQpEb2luZyBwYXJhbWV0ZXIgdHVuaW5nDQpgYGB7cn0NCiNmaW5kIGJlc3QgbnJvdW5kDQpjdjwteGdiLmN2KCBwYXJhbXMgPSBwYXJhbXMsIGRhdGEgPSBkdHJhaW4sIG5yb3VuZHMgPSA1MCwgbmZvbGQgPSA1LGdhbW1hPTAsIHNob3dzZCA9IFQsIHN0cmF0aWZpZWQgPSBULCBwcmludC5ldmVyeS5uID0gMTAsIGVhcmx5LnN0b3Aucm91bmQgPSAyMCwgbWF4aW1pemUgPSBGKQ0KY3YkYmVzdF9pdGVyYXRpb24NCnByaW50KGN2KQ0KcHJpbnQoY3YsIHZlcmJvc2U9VFJVRSkNCmBgYA0KQXMgd2UgaW4gdGhlIGFib3ZlIG91dHB1dCB3ZSBnb3QgbWluaW11bSBlcnJvciBpdGVyYXRpb24gNTAuDQoNCk5vdyB0cmFpbmluZyB0aGUgbW9kZWwgb24gdHJhaW4gZGF0YSBzZXQuDQpgYGB7cn0NCiNmaXJzdCBkZWZhdWx0IC0gbW9kZWwgdHJhaW5pbmcNCnhnYjEgPC0geGdiLnRyYWluIChwYXJhbXMgPSBwYXJhbXMsIGRhdGEgPSBkdHJhaW4sIG5yb3VuZHMgPSA1MCwgd2F0Y2hsaXN0ID0gbGlzdCh2YWw9ZHRlc3RmaW5hbCx0cmFpbj1kdHJhaW4pLCBwcmludC5ldmVyeS5uID0gMTAsIGVhcmx5LnN0b3Aucm91bmQgPSAxMCwgbWF4aW1pemUgPSBGICwgZXZhbF9tZXRyaWMgPSAibWxvZ2xvc3MiKQ0KYGBgDQpOb3cgd2UgYXJlIHVzaW5nIG91ciBtb2RlbCBvbiB0ZXN0IGRhdGEgc2V0Lg0KYGBge3J9DQojbW9kZWwgcHJlZGljdGlvbg0KeGdicHJlZCA8LSBwcmVkaWN0ICh4Z2IxLGR0ZXN0ZmluYWwpDQpgYGANCg0KI0NvbmZ1c2lvbiBNYXRyaXgNCmNoZWNraW5nIHRoZSByZXN1bHRzIG9mIHRoZSBtb2RlbC4NCmBgYHtyfQ0KcmVzdWx0PC1jb25mdXNpb25NYXRyaXgodGFibGUoYXMuZmFjdG9yKHRlc3RfdHJhaW5fZGF0YSRzdXJmYWNlKSwgYXMuZmFjdG9yKHhnYnByZWQpKSxtb2RlID0gInByZWNfcmVjYWxsIikNCnJlc3VsdA0KYGBgDQpPdXIgTW9kZWwgaGFzIGdpdmVuIGFjY3VyYWN5IG9mIDg4JS4NCg0KDQpUaGUgaW1wb3J0YW50IGZlYXR1cmVzIGdpdmVuIGJ5IFhHQm9vc3QgDQpgYGB7cn0NCnhnYi5pbXBvcnRhbmNlKCBtb2RlbCA9eGdiMSkNCmBgYA0KQXMgd2Ugc2VlIGFib3ZlIHRoZSBvcmllbnRhdGlvbl94IGlzIHRoZSBtb3N0IGltcG9ydGFudCBmZWF0dXJlIGZvciBwcmVkaWN0aW5nIHRoZSB0eXBlIG9mIGZsb29yLg0KDQpOb3cgd2UgYXJlIGdvaW5nIHRvIHVzZSBvdXIgbW9kZWwgZm9yIHByZWRpY3RpbmcgdGhlIHRlc3QgZGF0YS4NCnByZXByb2Nlc3NpbmcgdGhlIHRlc3QgZGF0YS4NCmBgYHtyfQ0KZHRlc3RmaW5hbDwteGdiLkRNYXRyaXgoYXMubWF0cml4KHRlc3QpKQ0KYGBgDQoNCg0KI1VzaW5nIHRoZSBtb2RlbCBmb3IgVGVzdCBEYXRhDQpwcmVkaWN0aW5nIHRoZSB2YWx1ZXMgZm9yIHRoZSBUZXN0IGRhdGEgLg0KYGBge3J9DQpwcmVkaWN0ZWRfdmFsdWU8LXByZWRpY3QgKHhnYjEsZHRlc3RmaW5hbCkNCmNsYXNzKHByZWRpY3RlZF92YWx1ZSkNCmBgYA0KRnVuY3Rpb24gZm9yIGRlY29kaW5nIHRoZSB2YXJpYWJsZXMuIA0KYGBge3J9DQpEZWNvZGluZzwtZnVuY3Rpb24oeCl7DQogIGlmKHg9PTApew0KICAgIHJldHVybigiY2FycGV0IikNCiAgfWVsc2UgaWYoeD09MSl7DQogICAgcmV0dXJuKCJjb25jcmV0ZSIpDQogIH1lbHNlIGlmKHg9PTIpew0KICAgIHJldHVybigiZmluZV9jb25jcmV0ZSIpDQogIH1lbHNlIGlmKHg9PTMpew0KICAgIHJldHVybigiaGFyZF90aWxlcyIpDQogIH1lbHNlIGlmKHg9PTQpew0KICAgIHJldHVybigiaGFyZF90aWxlc19sYXJnZV9zcGFjZSAiKQ0KICB9ZWxzZSBpZih4PT01KXsNCiAgICByZXR1cm4oInNvZnRfcHZjIikNCiAgfWVsc2UgaWYoeD09Nil7DQogICAgcmV0dXJuKCJzb2Z0X3RpbGVzIikNCiAgfWVsc2UgaWYoeD09Nyl7DQogICAgcmV0dXJuKCJ0aWxlZCIpDQogIH1lbHNlew0KICAgIHJldHVybigid29vZCIpDQogIH0NCn0NCg0KYGBgDQoNCmNhcnBldCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAwDQpjb25jcmV0ZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMQ0KZmluZV9jb25jcmV0ZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDINCmhhcmRfdGlsZXMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAzDQpoYXJkX3RpbGVzX2xhcmdlX3NwYWNlICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNA0Kc29mdF9wdmMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDUNCnNvZnRfdGlsZXMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA2DQp0aWxlZCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNw0Kd29vZCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDgNCg0KTm93IHdlIGFyZSBkb2luZyBEZWNvZGluZyBvdXIgdGFyZ2V0IHZhcmlhYmxlIHRvIHRoZWlyIHJlc3BlY3RpdmUgY2F0ZWdvcmllcyBnaXZlbiBhYm92ZSAuDQpgYGB7cn0NCnByZWRpY3RlZF92YWx1ZTwtc2FwcGx5KHByZWRpY3RlZF92YWx1ZSxEZWNvZGluZykNCmBgYA0KDQpzbyBGaW5hbCBwcmVkaWN0aW9ucyBhcmUgOi0NCmBgYHtyfQ0KdGVzdCRzdXJmYWNlPC1hcy5mYWN0b3IocHJlZGljdGVkX3ZhbHVlKQ0KYGBgDQoNClZpZXdpbmcgdGhlIHRlc3QgZGF0YSBhZnRlciBwcmVkaWN0aW9ucy4NCg0KI1RoZSBPdXRQdXQuDQpUaGlzIGlzIHRoZSBmb2xsb3dpbmcgZXhwZWN0ZWQgb3V0cHV0Lg0KYGBge3J9DQp0ZXN0WyxjKCJzZXJpZXNfaWQiLCJzdXJmYWNlIildDQpgYGANCg0K